/*
 * leftistheap.h
 *
 *  Created on: 2011-8-24
 *      Author: jfhu
 */

#ifndef LEFTISTHEAP_H_
#define LEFTISTHEAP_H_

#include "list.h"

typedef struct _item {
	int rank;
	int value;
	struct _item* leftChild;
	struct _item* rightChild;
} item, *pItem;

typedef struct _heap {
	pItem root;
} heap, *pHeap;

typedef struct _heaplistnode {
	pHeap h;
	struct _heaplistnode* next;
} heaplistnode, *pHeaplistnode;

typedef struct _heaplist {
	pHeaplistnode head;
	pHeaplistnode tail;
	int size;
} heaplist, *pHeaplist;

typedef struct _itemnode {
	pItem i;
	struct _itemnode* next;
} itemnode, *pItemnode;

typedef struct _itemnodelist {
	pItemnode head;
	pItemnode tail;
} itemnodelist, *pItemnodelist;


/* Initialize the heaplistnode */
void initializeheaplistnode(pHeaplistnode n);

/* Initialize the heaplistnode with a heap */
void initializeheaplistnode1(pHeaplistnode n, pHeap h);

/* Free a heap list node */
void freeheaplistnode(pHeaplistnode n);

/* Initialize the heap list */
void initializeheaplist(pHeaplist l);

/* Push back a heap on a heap list */
void push_back(pHeap h, pHeaplist l);

/* Pop the first heap on a heap list */
pHeap pop(pHeaplist l);


/* Initialize item */
void initializeitem(pItem i);

/* Free item */
void freeitem(pItem i);

/* Duplicate item */
pItem duplicate(const pItem i);

/* Initialize heap */
void initializeheap(pHeap h);

/* Initialize item list */
void initializeitemnodelist(pItemnodelist l);

/* Initialize item node */
void initializeitemnode(pItemnode n);

/* Initialize item node with item */
void initializeitemnode1(pItemnode n, pItem i);

/* Free item node */
void freeitemnode(pItemnode n);

/* Find the minimum value of heap */
pItem findmin(pHeap h);

/* Get a new heap melded with h1, h2 */
pHeap meld(pHeap h1, pHeap h2);

/* Mesh two items */
pItem mesh(pItem i1, pItem i2);

/* Insert the item into heap */
void insert(pItem i, pHeap h);

/* Delete and return the minimum value of heap */
pItem deletemin(pHeap h);

/* Return a list containing all items in heap h with key not exceeding real number x */
void listmin(pList l, int x, pItem i);

/* Return a heap formed by melding all the heaps on the list q */
pHeap heapify(pHeaplist q);

/* Make a heap */
pHeap makeheap(int *arr, int n);

/* Push back item into a heap acting as a list */
void push_backitem(pItem i, pItemnodelist l);

/* Pop up an item from a heap acting as a list */
pItem pop_item(pItemnodelist l);

/* Printf a heap */
void printfHeap(pHeap p);

/* Printf a item */
void printfItem(pItem i);


#endif /* LEFTISTHEAP_H_ */
